#include <iostream>
#include <math.h>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <sstream>
#include <algorithm>
#include <assert.h>

using namespace std;

// forn : for ( i en [0,n) )
#define forn( i,n ) for ( int i=0; i<(int)(n); i++ )
// fornin : for ( i en [desde,hasta) )
#define fornin(i, desde, hasta) for ( int i=(desde); i<(int)(hasta); i++ )
// decl : Declara la variable v igual que c
#define decl(v, c) typeof(c) v = c
// forall : foreach( i in c)
#define forall(i, c) for(decl(i, c.begin()); i!=c.end(); ++i)
// forall : foreach( i,j in c) talque i != j
#define forallDist(i, j , c) for(decl(i, c.begin()); ((++i)--) != c.end(); i++) for(decl(j, ((++i)--)); j != c.end(); j++)

typedef pair<int,int> intervalo;

int base = 2;

float logEnBase(int n,int  base) {
	return log10(n) / log10(base);
}

int potencia(int base,int exp) {
	return (int)pow(base, exp);
}

int main() {
    int cantidad_elementos = 0;
    int cantidad_busquedas = 0;

    while(cin >> cantidad_elementos && cantidad_elementos > 0) {
        cin >> cantidad_busquedas;

        /** Creo el arreglo de los elementos agrupados apartir del original **/
        /** 1. Recorrer los numeros y generar un arreglo con los numeros comprimidos
			de forma tal que este nuevo tenga la cantidad de repetidos seguidos.
			2. Guardar un mapeo de las posiciones originales al nuevo arreglo.
			3. Guardar una referencia de los intervalos de numeros repetidos.**/
        int elementos_agrupados[cantidad_elementos];    // Array de cantidades de elementos seguidas
        intervalo intervalos[cantidad_elementos];       // Array de mapeo de intervalo en cada grupo de lementos
        int posiciones_en_elem_agrupados[cantidad_elementos];   // Mapeo de la posicion original a la nueva.

        int elemento_anterior;
        int elemento_actual;
        int cantidad_actual;
        int principio_intervalo, final_intervalo; // Intervalo cerrado
        int posicion_actual_elementos_agrupados = 0;
        int posicion_en_elem_agrupados = 0;

        cin >> elemento_anterior;
        cantidad_actual = 1;
        principio_intervalo = 0;

        fornin(i, 1, cantidad_elementos) {
            cin >> elemento_actual;
            posiciones_en_elem_agrupados[posicion_en_elem_agrupados] = posicion_actual_elementos_agrupados;
            if(elemento_actual == elemento_anterior) {
                cantidad_actual++;
            } else {
                final_intervalo = posicion_en_elem_agrupados;
                elementos_agrupados[posicion_actual_elementos_agrupados] = cantidad_actual;
                intervalos[posicion_actual_elementos_agrupados] = intervalo(principio_intervalo, final_intervalo);
                cantidad_actual = 1;
                posicion_actual_elementos_agrupados++;
                principio_intervalo = posicion_en_elem_agrupados + 1;
            }
            elemento_anterior = elemento_actual;
            posicion_en_elem_agrupados++;
        }

        final_intervalo = posicion_en_elem_agrupados;
        posiciones_en_elem_agrupados[posicion_en_elem_agrupados] = posicion_actual_elementos_agrupados;
        elementos_agrupados[posicion_actual_elementos_agrupados] = cantidad_actual;
        intervalos[posicion_actual_elementos_agrupados] = intervalo(principio_intervalo, final_intervalo);
        posicion_actual_elementos_agrupados++;
		/** ------------------ Fin armar arreglo --------------------**/
		
		/** 4. Calcular el maximo de a pares del arreglo nuevo y
		    de forma iterativa sobre el recien calculados. **/
        int cantidad_elementos_agrupados = posicion_actual_elementos_agrupados;

        int log_cant_elem = max((int)(1), (int)ceil(logEnBase(cantidad_elementos_agrupados, base)));

        int maximos[cantidad_elementos][log_cant_elem];

        forn(i, cantidad_elementos_agrupados) forn(j, log_cant_elem) {
            maximos[i][j] = 0;
            if (j == 0) maximos[i][j] = elementos_agrupados[i];
        }
		
        int tam_intervalo =  1;
        fornin(pot, 1, log_cant_elem) {
            int tam_intervalo_anterior = tam_intervalo;
            tam_intervalo *= base;
            int potencia_anterior = pot -1;

            forn(pos, cantidad_elementos_agrupados) {

                int principio_anterior_1    = pos;
                int final_anterior_1        = principio_anterior_1 + tam_intervalo_anterior - 1;
                int principio_anterior_2    = final_anterior_1 + 1;
                int final_anterior_2        = principio_anterior_2 + tam_intervalo_anterior - 1;

                int el_maximo = 0;
                if(final_anterior_2 < cantidad_elementos_agrupados) {
                    el_maximo = max(   maximos[principio_anterior_1][potencia_anterior],
                                       maximos[principio_anterior_2][potencia_anterior]);
                }
                maximos[pos][pot] = el_maximo;
            }
        }
        /** ---------------- Fin calcular maximos -------------------**/
        
		// PASO 5: Para cada intervalo en el conjunto de busqueda.
        forn(busqueda_k, cantidad_busquedas) {
            int desde, hasta, diferencia;
            cin >> desde >> hasta;

            desde--;
            hasta--;
            
			// PASO 6 y 7: obtener maximo de los bordes
            int max_principio = 0;
            int posicion_en_elem_agrup_desde = posiciones_en_elem_agrupados[desde];
            if(intervalos[posicion_en_elem_agrup_desde].first != desde){
                max_principio = min(intervalos[posicion_en_elem_agrup_desde].second, hasta) - desde + 1;
                desde = intervalos[posicion_en_elem_agrup_desde].second + 1;
            }

            int max_final = 0;
            int posicion_en_elem_agrup_hasta = posiciones_en_elem_agrupados[hasta];
            if(intervalos[posicion_en_elem_agrup_hasta].second != hasta){
                max_final = hasta - max(intervalos[posicion_en_elem_agrup_hasta].first, desde) + 1;
                hasta = intervalos[posicion_en_elem_agrup_hasta].first - 1;
            }

			// PASO 8: obtener maximo del medio
            int cantidad_maxima = 1;
            diferencia = hasta - desde + 1 ;
            if(diferencia > 0) {
                desde = posiciones_en_elem_agrupados[desde];
                hasta = posiciones_en_elem_agrupados[hasta];
                diferencia = hasta - desde + 1 ;

                int potencia_anterior = max(int(0), (int)floor(logEnBase(diferencia, base)));
                int tam_intervalo = max(int(0), potencia(base, potencia_anterior));
                int desplazamiento = diferencia - tam_intervalo;
                int desde_2 = desde + desplazamiento;

                cantidad_maxima = max(maximos[desde][potencia_anterior], maximos[desde_2][potencia_anterior]);
            }

			// PASO 9:
            cantidad_maxima = max(cantidad_maxima, max_principio);
            cantidad_maxima = max(cantidad_maxima, max_final);

            cout << cantidad_maxima << endl;
        }
    }

    return 0;
}
